package com.mdnote.practice.dfs_bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/16
 * @description 二叉树的层序遍历
 */
public class LeetCode102 {

    public static void main(String[] args) {
        LeetCode102 leetCode102 = new LeetCode102();
        TreeNode root = new TreeNode(55);
        root.left = new TreeNode(22);
        root.right = new TreeNode(77);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(30);
        List<List<Integer>> res = leetCode102.levelOrder(root);
        res.forEach(System.out::println);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
//        bfs(root, resList);
        dfs(root, 0,  resList);
        return resList;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> resList) {

        // Terminator
        if (node == null) {
            return;
        }
        // process
        if (resList.size() < level + 1) {
            resList.add(level, new ArrayList<>());
        }
        resList.get(level).add(node.val);

        dfs(node.left, level + 1, resList);
        dfs(node.right, level + 1, resList);
    }

    private void bfs(TreeNode node, List<List<Integer>> resList) {

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            // 这里一次直接处理完当前层的全部节点
            List<Integer> res = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode tempNode = queue.removeFirst();
                if (tempNode.left != null) {
                    queue.addLast(tempNode.left);
                }
                if (tempNode.right!= null) {
                    queue.addLast(tempNode.right);
                }
                res.add(tempNode.val);
            }
            resList.add(res);
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
